/**
 * 面试题 17.19. 消失的两个数字
 * https://leetcode.cn/problems/missing-two-lcci/description/
 */
class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length;
        int tmp = 0;
        //数组内全部元素异或
        for(int x : nums) {
            tmp ^= x;
        }
        //1~n+2之间异或
        for(int i = 1; i <= n + 2; i++) {
            tmp ^= i;
        }
        //剩下消失的数字的异或和，二进制右边第一个是1和不是1就是消失的数字
        int lowbit = tmp & (-tmp);
        int[] ret = new int[2];
        //找出最右边的1在第几位
        int diff = 0;
        for(int i = 0; i < 32; i++) {
            if(((lowbit >> i) & 1) == 1) {
                diff = i;
                break;
            }
        }
        for(int i = 1; i <= n + 2; i++) {
            if(((i >> diff) & 1) == 1) ret[1] ^= i;
            else ret[0] ^= i;
        }
        for(int x : nums) {
            if(((x >> diff) & 1) == 1) ret[1] ^= x;
            else ret[0] ^= x;
        }
        return ret;
    }
}